'''
Created on Jul 1, 2011

@author: anupam saini
'''

from random import random as rd
from com.anupam.common.utils import Utils

"""
  Sorts only unique valued integers.
"""
class QuickSortSecApproach(object):
  
  def __init__(self):
    self.loopCount = 0
    pass

  def swap(self, arr, fromIndex, toIndex):
    temp = arr[fromIndex]
    arr[fromIndex] = arr[toIndex]
    arr[toIndex] = temp

  def partition(self, arr, left, right):
    size = right-left + 1
    if size < 2:
      return
    ind = left + int(rd()*(size-1))
    pivotVal = arr[ind]
    l = left
    u = right
    while l < u:
      while (arr[l] < pivotVal):
        self.loopCount = self.loopCount + 1
        l = l + 1
      while (arr[u] > pivotVal): 
        self.loopCount = self.loopCount + 1
        u = u - 1
      self.swap(arr, l, u)
    self.partition(arr, left, l)
    self.partition(arr, l + 1, right)

if __name__ == '__main__':
  short = QuickSortSecApproach()
  util = Utils()
  arr = util.generateNumbers(16)
  short.partition(arr, 0, len(arr) -1)
  print "post sort  : " + str(arr)
  print 'These many loops : ' + str(short.loopCount)